package niuke;

import niuke.common.TreeNode;

import java.util.*;

/**
 * NC15 求二叉树的层序遍历
 * 题目
 * 题解(156)
 * 讨论(274)
 * 排行
 * 中等  通过率：45.35%  时间限制：1秒  空间限制：64M
 * 知识点
 * 树
 * bfs
 * 描述
 * 给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
 * 例如：
 * 给定的二叉树是{3,9,20,#,#,15,7},
 *
 * 该二叉树层序遍历的结果是
 * [
 * [3],
 * [9,20],
 * [15,7]
 *
 * ]
 *
 *
 * 提示:
 * 0 <= 二叉树的结点数 <= 1500
 *
 *
 * 示例1
 * 输入：
 * {1,2}
 * 复制
 * 返回值：
 * [[1],[2]]
 * 复制
 * 示例2
 * 输入：
 * {1,2,3,4,#,#,5}
 * 复制
 * 返回值：
 * [[1],[2,3],[4,5]]
 * */

public class SequenceTraversalOfBinaryTree {
    public static void main(String[] args) {
        TreeNode root = new TreeNode();
        root.val = 1;
        TreeNode node2 = new TreeNode();
        node2.val = 2;
        TreeNode node3 = new TreeNode();
        node3.val = 3;
        TreeNode node4 = new TreeNode();
        node4.val = 4;
        TreeNode node5 = new TreeNode();
        node5.val = 5;
        TreeNode node6 = new TreeNode();
        node6.val = 6;
        root.left = node2;
        root.right = node3;
        node2.left = node4;
        node3.left = node5;
        node3.right = node6;
        SequenceTraversalOfBinaryTree sequenceTraversalOfBinaryTree = new SequenceTraversalOfBinaryTree();
        ArrayList<ArrayList<Integer>> arrayLists = sequenceTraversalOfBinaryTree.levelOrder(root);
        System.out.println(arrayLists);
    }
    /**
     *
     * @param root TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {

        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        queue.add(node);

        while(!queue.isEmpty()){
            int length = queue.size();
            ArrayList<Integer> arrayList = new ArrayList<>();
            while (length -- > 0){
                node = queue.remove();
                arrayList.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            result.add(arrayList);
        }
        return result;
    }
}

